/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author ke.su date: 2019-06-13 Time: 下午9:24
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 横竖斜都不能攻击
 * <p>
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 * <p>
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * 输入: 4
 * 输出: [
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * <p>
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 * 解释: 4 皇后问题存在两个不同的解法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens
 */
public class Test55 {

    public static void main(String[] args) {
        List<List<String>> result = solveNQueens(5);

        System.out.println(JSON.toJSONString(result));

    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();


        List<P> ps = new ArrayList<>();

        //初始化棋盘对象
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                ps.add(new P(x, y, x - y, n - (x + y) - 1));
            }
        }

        //最大入口循环次数
        int num = n % 2 == 0 ? n / 2 : (n / 2 + 1);

        for (int k = 0; k < num; k++) {
            List<P> res = new ArrayList<>();
            diGui(ps.get(k), ps, res, n, 1, result);
        }

        return result;
    }

    private static void diGui(P p, List<P> ps, List<P> res, int n, int x, List<List<String>> result) {
        res.add(p);
        if(res.size() == n) {
            List<String> re = new ArrayList<>();
            List<String> ref = new ArrayList<>();

            int num = n % 2 == 0 ? n / 2 : (n / 2 + 1);

            for (int i = 0; i < n; i++) {
                String str = "";
                String strf = "";
                for (int j = 0; j < n; j++) {
                    if(j == res.get(i).y) {
                        str += "Q";
                        strf = "Q" + strf;
                    } else {
                        str += ".";
                        strf = "." + strf;
                    }
                }
                re.add(str);
                ref.add(strf);
            }
            result.add(re);
            if(n % 2 == 0 || res.get(0).y != (num-1)) {
                result.add(ref);
            }

            res.remove(res.size() - 1);
            return;
        }
        //排除相交的点
        List<P> ps1 = ps.stream().filter(p1 -> !(p1.x == p.x || p1.y == p.y || p1.xy == p.xy || p1.yx == p.yx))
                .collect(Collectors.toList());
        if(ps1.size() == 0) {
            res.remove(res.size() - 1);
            return;
        }
        int num = 0;
        while (ps1.size() > num && ps1.get(num).x == x) {
            diGui(ps1.get(num), ps1, res, n, x + 1, result);
            num++;
        }
        res.remove(res.size() - 1);
    }


}


class P {
    int x;
    int y;
    int xy;
    int yx;

    P(int x, int y, int xy, int yx) {
        this.x = x;
        this.y = y;
        this.xy = xy;
        this.yx = yx;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}